//**********************************************************************
//	Programmer	-	Sujal Bista
//	File Name	-	bucketList.h
//	Description	:	
//					bucket link list
//
//**********************************************************************


#ifndef _BUCKET_LINK_H
#define _BUCKET_LINK_H

//BUCKET link list

#include "global.h"


//link list class
template <typename T>
class bucketList
{
	
		class node
		{
			public:
				T* data;
				node *next;
				node *prev;
				unsigned int count;

				//constructor
				node(unsigned int bucketSize)
				{
					data=new T[bucketSize];
					prev=next=NULL;
					count=0;
				}

				//adds data to specified index
				void add(const T &cData, unsigned int index)
				{
					//move the data
					for(unsigned int i=count;i>index;i--)
						data[i]=data[i-1];

					//copy the data
					data[index]=cData;

					//increase the count
					count++;
				}

				//remove specified index
				bool remove(unsigned int index)
				{
					if(!count)
						return false;

					//move the data
					for(unsigned int i=index;i<count-1;i++)
						data[i]=data[i+1];

					//dencrease the count
					count--;

					return true;
				}
				
				//clear the data
				void clear(void)
				{
					if(data)
					{
						delete[] data;
						data=NULL;
					}
				}

				~node()	
				{
					clear();
				}
		};
	
		node *head;
		node *tail;
		unsigned int nodeCount;
		unsigned int dataCount;
		unsigned int bucketSize;
		

		//add node in the front of queue
		inline bool addNodeFront(node *data)
		{
			//setup head and tail
			if(!head)
				tail=data;
			else
			{
				data->next=head;
				head->prev=data;
			}
            head=data;
			nodeCount++;
			return true;
		}

		//add node at the end of the queue
		inline bool addNodeBack(node *data)
		{
			//setup head and tail
			if(!head)
				head=data;
			else 
			{
				tail->next=data;
				data->prev=tail;
			}
			tail=data;

			nodeCount++;
			return true;
		}

		//add node after current node
		inline bool addNodeAfter(node *refNode, node *data)
		{
			//setup head and tail
			if(!head)
			{
				head=data;
				tail=data;
			}
			else if(refNode==NULL)
			{
				refNode->next=head;
			}
			else 
			{
				data->prev=refNode;
				data->next=refNode->next;

				refNode->next=data;
				if(data->next)
					data->next->prev=data;
				else
					tail=data;
			}			

			nodeCount++;
			return true;
		}

		//remove node
		inline void removeNode(const unsigned int &index)
		{
			node *corpse=head,*prev=NULL;
			for(unsigned int i=0;i<index;i++)
			{
				prev=corpse;
				corpse=corpse->next;
			}
			if(prev==NULL)
			{
				head=corpse->next;
				if(head)
					head->prev=NULL;
			}
			else
			{
				prev->next=corpse->next;
				if(corpse->next)
					corpse->next->prev=prev;
			}
			//setup tail
			if(corpse==tail)
				tail=prev;
			nodeCount--;
			delete corpse;			
		}

		//remove node
		inline void removeNode(node *cNode)
		{
			node *corpse=cNode,*prev=cNode->prev;
			if(prev==NULL)
			{
				head=corpse->next;
				if(head)
					head->prev=NULL;
			}
			else
			{
				prev->next=corpse->next;
				if(corpse->next)
					corpse->next->prev=prev;
			}
			//setup tail
			if(corpse==tail)
				tail=prev;
			nodeCount--;
			delete corpse;			
		}

		//returns node that handles the given index, sum data is number of data before the current node
		inline node *getNode(unsigned int index, unsigned int &sumData)
		{
			sumData=0;
			if(head)
			{	
				for(node *currNode=head;currNode;currNode=currNode->next)
				{
					if(sumData+currNode->count>index)
						return currNode;
					sumData+=currNode->count;
				}
			}
			return NULL;
		}

		//returns the data at the given index
		inline T *getData(unsigned int index)
		{
			if(head)
			{		
				unsigned int sumData=0;
				for(node *currNode=head;currNode;currNode=currNode->next)
				{
					if(sumData+currNode->count>index)
						return &currNode->data[index-sumData];
					sumData+=currNode->count;
				}
			}
			return NULL;
		}

		//returns the data at the given index
		inline const T *getData(unsigned int index) const
		{
			if(head)
			{		
				unsigned int sumData=0;
				for(node *currNode=head;currNode;currNode=currNode->next)
				{
					if(sumData+currNode->count>index)
						return &currNode->data[index-sumData];
					sumData+=currNode->count;
				}
			}
			return NULL;
		}

		//descending order http://en.wikipedia.org/wiki/Selection_algorithm
		unsigned int partitionDescending(const unsigned int &left, const unsigned int &right, const unsigned int &pivotIndex)
		{
			T temp;
			T pivotValue = operator[](pivotIndex);

			SWAP(operator[](pivotIndex),operator[](right),temp);  // Move pivot to end

			unsigned int storeIndex = left;
			for(unsigned int i=left;i<right;i++)
			{
				if(operator[](i) > pivotValue)
				{
					SWAP(operator[](storeIndex),operator[](i),temp);
					storeIndex++;
				}
			}
			SWAP(operator[](right),operator[](storeIndex),temp); // Move pivot to its final place
			return storeIndex;
		}

		//descending order http://en.wikipedia.org/wiki/Quicksort
		void quickSortDescending(const unsigned int &left, const unsigned int &right)
		{
			if(left<right)
			{
				unsigned int pivotIndex = left;

				//find the index
				pivotIndex=partitionDescending(left, right, pivotIndex);

				//quick sort
				quickSortDescending(left,pivotIndex);
				quickSortDescending(pivotIndex+1,right);
			}
		}

		//ascending order http://en.wikipedia.org/wiki/Selection_algorithm
		unsigned int partitionAscending(const unsigned int &left, const unsigned int &right, const unsigned int &pivotIndex)
		{
			T temp;
			T pivotValue = operator[](pivotIndex);

			SWAP(operator[](pivotIndex),operator[](right),temp);  // Move pivot to end

			unsigned int storeIndex = left;
			for(unsigned int i=left;i<right;i++)
			{
				if(operator[](i) < pivotValue)
				{
					SWAP(operator[](storeIndex),operator[](i),temp);
					storeIndex++;
				}
			}
			SWAP(operator[](right),operator[](storeIndex),temp); // Move pivot to its final place
			return storeIndex;
		}

		//ascending order http://en.wikipedia.org/wiki/Quicksort
		void quickSortAscending(const unsigned int &left, const unsigned int &right)
		{
			if(left<right)
			{
				unsigned int pivotIndex = left;

				//find the index
				pivotIndex=partitionAscending(left, right, pivotIndex);

				//quick sort
				quickSortAscending(left,pivotIndex);
				quickSortAscending(pivotIndex+1,right);
			}
		}
				
	public:
		
		//default constructor
		bucketList(void)
		{
			head=tail=NULL;
			nodeCount=0;
			dataCount=0;
			bucketSize=1024;
		}

		//constructor
		bucketList(unsigned int bucketSize)
		{
			head=tail=NULL;
			nodeCount=0;
			dataCount=0;
			this->bucketSize=bucketSize;
		}

		//copy constructor
		bucketList(const bucketList &bData)
		{
			head=tail=NULL;
			nodeCount=0;
			dataCount=0;
			bucketSize=bData.getBucketSize();

			for(unsigned int i=0;i<bData.dataCount;i++)
				addBack(bData[i]);
		}

		//assignment operator
		const bucketList& operator=(const bucketList& bData)
		{
			if(this!=((const bucketList *)&bData))
			{
				clear();

				bucketSize=bData.getBucketSize();

				for(unsigned int i=0;i<bData.dataCount;i++)
					addBack(bData[i]);
			}
			return *this;
		}

		//indexing
		inline T& operator[](const unsigned int& index)
		{
			return  *getData(index);
		}

		//indexing
		inline const T& operator[](const unsigned int& index) const
		{
			return *getData(index);
		}

		//add node at the end of the queue
		bool addFront(const T &data)
		{
			//if the head do not exist or if there is not any empty space
			if(!head || head->count>=bucketSize)
				addNodeFront(new node(bucketSize));
			
			//add the data into the tail
			head ->add(data,0);

			dataCount++;
			return true;
		}
				
		//add node at the end of the queue
		bool addBack(const T &data)
		{
			//if the head do not exist or if there is not any empty space
			if(!head || tail->count>=bucketSize)
				addNodeBack(new node(bucketSize));
			
			//add the data into the tail
			tail->add(data,tail->count);

			dataCount++;
			return true;
		}
		
		//add node at the end of the queue
		bool add(const T &data,unsigned int index=0)
		{
			unsigned int sumData=0;
			//find where to insert
			node *insertNode=getNode(index,sumData);

			//if node needs to be added (two cases)
			if(insertNode)
			{
				//we have to do nothing
				if(insertNode->count>=bucketSize)
				{
					//insert a node and send the pointer back
					node *newNode=new node(bucketSize);

					//add node after current node
					addNodeAfter(insertNode, newNode);
					
					//move the last element to next node
					newNode->add(insertNode->data[insertNode->count-1],0);
					insertNode->count--;
				}

			}
			else if(index==0) //the insert point is at the front
			{
				//is the insert Node is blank add one
				addNodeBack(new node(bucketSize));

				//assign the tail to insert node
				insertNode=head;
			}
			else	//there will be two cases either (there are no nodes) or (the insert location is at the end of the list)
			{
				if(!(tail && tail->count<bucketSize))
				{
					//is the insert Node is blank add one
					addNodeBack(new node(bucketSize));
				}
				
				//assign the tail to insert node
				insertNode=tail;

				//we do not want to count the number of data in the current thread
				sumData-=tail->count;
			}

			//add the data
			insertNode->add(data,index-sumData);

			//add the data
			dataCount++;

			return true;
		}

		//add lot of data at a time
		bool add(const T *dData,unsigned int count)
		{
			unsigned int tempDataCount=count;
			unsigned int dataAdded=0;
			while(dataAdded<tempDataCount)
			{
				//check the tail and no of empty slots in it.
				if(tail==NULL || bucketSize<=tail->count)
					addNodeBack(new node(bucketSize));	//add the node

				//get the last node
				node *currNode=tail;

				//get the number of slots that needs to be filled
				unsigned int emptySlots=bucketSize-currNode->count;

				//total number of data left to be added
				unsigned int dataLeft=tempDataCount-dataAdded;

				//number of data that will be added to current node
				unsigned int dataToAddForCurrentNode=MIN(emptySlots,dataLeft);
				
				for(unsigned int j=0;j<dataToAddForCurrentNode;j++)
					currNode->data[currNode->count+j]=dData[dataAdded+j];

				//find the number data in ther current node
				currNode->count=MIN(bucketSize,currNode->count+dataToAddForCurrentNode);
				
				//incecrease the amount of data left to read
				dataAdded+=dataToAddForCurrentNode;
			}			

			//increase the datacount by the number of data added
			dataCount+=dataAdded;

			return true;
		}

		//remove node
		inline void remove(const unsigned int &index)
		{
			if(head)
			{		
				unsigned int sumData=0;
				for(node *currNode=head;currNode;currNode=currNode->next)
				{
					if(sumData+currNode->count>index)
					{
						//remove the data
						if(currNode->remove(index-sumData))
						{
							dataCount--;
							if(currNode->count==0)
								removeNode(currNode);
						}
						return;
					}
					sumData+=currNode->count;
				}
			}
		}
				
		//return data count
		inline unsigned int size(void) const
		{
			return dataCount;
		}

		//return bucket size
		inline unsigned int getBucketSize(void) const
		{
			return bucketSize;
		}
				
		//perform quick sort of the data
		void sort(bool ascendingOrder=true)
		{
			if(ascendingOrder)
				quickSortAscending(0,dataCount-1);
			else
				quickSortDescending(0,dataCount-1);
		}

		//searches for the data
		T *find(const T &dData)
		{
			for(unsigned int i=0;i<dataCount;i++)
			{
				T *currDataPtr=getData(i);
				if(*currDataPtr==dData)
					return currDataPtr;
			}
			return NULL;
		}

		//clear the list
		void clear(void)
		{
			node *corpse=head,*hold=NULL;
			while(corpse)
			{
				hold=corpse;
				corpse=corpse->next;
				delete hold;
			}
			tail=head=NULL;
			nodeCount=0;
			dataCount=0;
		}

		//destructor
		~bucketList()
		{
			clear();
		}

		//compacts the data
		void compact(void)
		{
			//move the data forward
			for(node *currNode=head;currNode;currNode=currNode->next)
			{
				//check if the next node exists and if the current one is not filled
				while(currNode->next && currNode->count<bucketSize)
				{
					//get the next node
					node* nextNode=currNode->next;
					
					//get the number of slots that needs to be filled
					unsigned int emptySlots=bucketSize-currNode->count;
					for(unsigned int i=0;i<emptySlots && nextNode->count ;i++)
					{
						currNode->add(nextNode->data[0],currNode->count);	//add the content to the curr node
						nextNode->remove(0);	//remove the content
					}

					//if the next node does not have any data remove it
					if(nextNode->count==0)
						removeNode(nextNode);
				}
			}
		}

		//reads compact content in the file
		bool read(char *fileName)
		{
			std::ifstream in(fileName,std::ios::binary);
			if(!in)
				return false;

			unsigned int tempDataCount;
			unsigned int dataAdded=0;

			//read the data count
			in.read((char *)&tempDataCount,sizeof(unsigned int));
			
			while(dataAdded<tempDataCount)
			{
				//check the tail and no of empty slots in it.
				if(tail==NULL || bucketSize<=tail->count)
					addNodeBack(new node(bucketSize));	//add the node

				//get the last node
				node *currNode=tail;

				//get the number of slots that needs to be filled
				unsigned int emptySlots=bucketSize-currNode->count;

				//total number of data left to be added
				unsigned int dataLeft=tempDataCount-dataAdded;

				//number of data that will be added to current node
				unsigned int dataToAddForCurrentNode=MIN(emptySlots,dataLeft);
				
				//read the contents, one node at the time
				in.read((char *)&currNode->data[currNode->count],sizeof(T)*dataToAddForCurrentNode);

				//find the number data in ther current node
				currNode->count=MIN(bucketSize,currNode->count+dataToAddForCurrentNode);
				
				//incecrease the amount of data left to read
				dataAdded+=dataToAddForCurrentNode;
			}			

			//increase the datacount by the number of data added
			dataCount+=dataAdded;

			in.close();
			return true;
		}

		//writes compact content in the file
		bool write(char *fileName)
		{
			//compacts the data
			compact();

			std::ofstream out(fileName,std::ios::binary);
			if(!out)
				return false;

			//write the content
			if(head)
			{	
				//write the datat count
				out.write((const char *)&dataCount,sizeof(unsigned int));

				//write the contents, one node at the time
				for(node *currNode=head;currNode;currNode=currNode->next)
					out.write((const char *)currNode->data,sizeof(T)*currNode->count);
			}
			out.close();
			return true;
		}

		//prints to the output stream
		friend std::ostream& operator<<(std::ostream &out, const bucketList<T>& bData)
		{
			out<<bData.dataCount<<"\n";
			
			for(unsigned int i=0;i<bData.dataCount;i++)
				out<<bData[i]<<"\n";

			return out;
		}
		//reads from the input stream
		friend std::istream& operator>>(std::istream &in, bucketList<T>& bData)
		{
			unsigned int dataCount;
			T temp;
			
			in>>dataCount;
			for(unsigned int i=0;i<dataCount;i++)
			{
				in>>temp;//read the file
				bData.addBack(temp);//add at the end
			}
			return in;
		}
};


#endif
